package leetcode;

/**
 * Created by lyk on 2019-2-6.
 * Package name: leetcode
 * Porject name: untitled1
 */



//编写一个遍历游程编码序列的迭代器。
//
//        迭代器由RLEIterator(int[] A)初始化，其中A是某个序列的游程编码。更具体地，对于所有偶数 i，A[i] 告诉我们在序列中重复非负整数值 A[i + 1] 的次数。
//
//        迭代器支持一个函数：next(int n)，它耗尽接下来的n个元素（n >= 1）并返回以这种方式耗去的最后一个元素。如果没有剩余的元素可供耗尽，则 next返回-1。
//
//        例如，我们以A = [3,8,0,9,2,5]开始，这是序列 [8,8,8,5,5] 的游程编码。这是因为该序列可以读作 “三个零，零个九，两个五”。
//
//        示例：
//
//        输入：["RLEIterator","next","next","next","next"], [[[3,8,0,9,2,5]],[2],[1],[1],[2]]
//        输出：[null,8,8,5,-1]
//        解释：
//        RLEIterator 由 RLEIterator([3,8,0,9,2,5]) 初始化。
//        这映射到序列 [8,8,8,5,5]。
//        然后调用 RLEIterator.next 4次。
//
//        .next(2) 耗去序列的 2 个项，返回 8。现在剩下的序列是 [8, 5, 5]。
//
//        .next(1) 耗去序列的 1 个项，返回 8。现在剩下的序列是 [5, 5]。
//
//        .next(1) 耗去序列的 1 个项，返回 5。现在剩下的序列是 [5]。
//
//        .next(2) 耗去序列的 2 个项，返回 -1。 这是由于第一个被耗去的项是 5，
//        但第二个项并不存在。由于最后一个要耗去的项不存在，我们返回 -1。
//
//        PS:Leetcode这次的竞赛时间是1小时45分钟是因为竞赛开始了10分钟，但是题目还是看不到
//
//        解题思路
//
//        其实一开始做这个题目的时候我也是一头雾水，首先游程编码是一个我没接触过的概念，其次是这个题目描述说得太绕了。关于游程编码的概念，可以从网上找到介绍。
//
//        我先从示例入手简单讲解一下题目：
//
//        首先我们要知道关于初始化的数组其实是经过游程编码处理后的数组，即压缩后的数组。先展示游程编码前后的数组：
//
//        编码后
//        [3,8,0,9,2,5]
//
//        编码前
//        [8,8,8,5,5]
//
//        根据题目的介绍，对编码后的数组进行处理后：[(3,8),(0,9),(2,5)]。每个括号内的其实就是(数字出现次数,对应的数字).也就是题目中所说的:
//
//        对于所有偶数 i，A[i] 告诉我们在序列中重复非负整数值 A[i + 1] 的次数。
//
//        然后我们可以尝试进行解码：
//
//        解码(3,8)得到数组[8,8,8]
//        解码(0,9),由于次数为0，所以结果为[]
//        解码(2,5)得到[5,5]
//        然后按照顺序拼接起来[8,8,8,5,5]
//
//        而题目其实是要求我们根据输入的编码后的数组遍历解码(编码前)的数组
public class RLEIterator {
    int[] A;
    int i, q;

    public RLEIterator(int[] A) {
        this.A = A;
        i = q = 0;
    }

    public int next(int n) {
        while (i < A.length) {
            if (q + n > A[i]) {
                n -= A[i] - q;
                q = 0;
                i += 2;
            } else {
                q += n;
                return A[i+1];
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        RLEIterator rlei = new RLEIterator(new int[]{3, 8, 0, 9, 2, 5});
        System.out.println(rlei.next(2));
        System.out.println(rlei.next(1));
        System.out.println(rlei.next(1));
        System.out.println(rlei.next(2));

    }

}
